Establishing a Peer-to-Peer (P2P) communication path between two hosts across packet networks can be challenging when one or both of the hosts are connected to the packet network through Network Address Translation (NAT) or firewalls. The hosts attempt to ascertain public addresses to establish a P2P communication session. However, when both hosts are connected through NAT, these attempts often fail to establish a direct connection between the P2P hosts, and a relay must be used to establish the P2P communication session. The relay is a host on an open network that relays communication packets between the P2P hosts. All traffic between the peer hosts passes through the relay at the expense of network bandwidth and processing at the relay host. As the number of hosts connected through NAT in a P2P network increases, more relay hosts are needed to provide capacity for relaying traffic in the P2P network.